#!/usr/bin/env python
#-*- coding:utf-8 -*-
#$Id:

from math import sqrt

class NotImplement(Exception):
	"""
	An not implement exception
	"""

class Similarity(object):
	def __init__(self, prefs, item1, item2):
		super(Similarity, self).__init__()

		self._len = 0
		self._si = ()
		self._d1 = {}
		self._d2 = {}

		self._prepare(prefs, item1, item2)
	
	def _prepare(self, prefs, item1, item2):
		self._si = set(prefs[item1].keys()) & set(prefs[item2].keys())
		self._len = len(self._si)

		for item in self._si:
			self._d1[item] = prefs[item1][item]
			self._d2[item] = prefs[item2][item]

	def similarity(self):
		"""
		定义为纯虚函数，需继承类实现
		"""
		raise NotImplement()

###
class EucDistance(Similarity):
	"""
	简单欧拉距离 《PCI》
	"""
	def __init__(self, prefs, item1, item2):
		super(EucDistance, self).__init__(prefs, item1, item2)
	
	def similarity(self):
		if self._len == 0:
			return 0
		sum_of_square = sum(pow(self._d1[k] - self._d2[k], 2) for k in self._si)
		return 1 / float(1 + sum_of_square)


class Pearson(Similarity):
	"""
	皮尔森相关系数 《PCI》 
	"""
	def __init__(self, prefs, item1, item2):
		super(Pearson, self).__init__(prefs, item1, item2)
	
	def similarity(self):
		if self._len == 0:
			return 0
		sum1 = sum(self._d1.values())
		sum2 = sum(self._d2.values())

		sum1_sq = sum([pow(v, 2) for v in self._d1.values()])
		sum2_sq = sum([pow(v, 2) for v in self._d2.values()])

		p_sum = sum([self._d1[k]*self._d2[k] for k in self._si])

		num = p_sum - (float(sum1 * sum2) / self._len)
		den = sqrt((sum1_sq - float(pow(sum1, 2)) / self._len) * (sum2_sq - float(pow(sum2, 2)) / self._len))
		if den == 0:
			return 0
		
		return num / den

class Pearson2(Similarity):
	"""
	该公式和PCI中的公式不同，也是计算皮尔森系数，根据公式翻成代码
	《数据挖掘导论》
	经过1／2个数据集的检验，竟然和上面的皮尔森算出来的结果完全相同
	"""
	def __init__(self, prefs, item1, item2):
		super(Pearson2, self).__init__(prefs, item1, item2)
	
	def similarity(self):
		if self._len == 0:
			return 0

		#计算均值	
		avg_x = float(sum(self._d1.values())) / self._len
		avg_y = float(sum(self._d2.values())) / self._len

		#计算协方差
		s_xy = sum([(self._d1[k] - avg_x) * (self._d2[k] - avg_y) for k in self._si])
		#计算x／y的均方差
		s_x = sum([pow((v - avg_x), 2) for v in self._d1.values()])
		s_y = sum([pow((v - avg_y), 2) for v in self._d2.values()])
		den = sqrt(s_x * s_y)
		if den == 0:
			return 0

		return s_xy / den 
	
class Cosine(Similarity):
	"""
	计算余弦相似度，如果余弦相似度为1，则两向量夹角为0；相似度为0，则夹角为90度
	《数据挖掘导论》
	"""
	def __init__(self, prefs, item1, item2):
		super(Cosine, self).__init__(prefs, item1, item2)

	def similarity(self):
		if self._len == 0:
			return 0

		#求向量的点积和两个向量的模，然后相除
		xy = sum([self._d1[k] * self._d2[k] for k in self._si])
		mx = sqrt(sum([pow(v, 2) for v in self._d1.values()])) 
		my = sqrt(sum([pow(v, 2) for v in self._d2.values()]))

		return xy / (mx * my)

"""
Jaccard相似度处理非对称二元属性，故不适合评分系统，暂不实现
class Jaccard(Similarity):
"""

class Tanimoto(Similarity):
	"""
	广义Jaccard系数，又叫Tanimoto系数，在二元属性下归约为Jaccard系数
	《数据挖掘导论》
	"""
	def __init__(self, prefs, item1, item2):
		super(Tanimoto, self).__init__(prefs, item1, item2)

	def similarity(self):
		if self._len == 0:
			return 0

		xy = sum([self._d1[k] * self._d2[k] for k in self._si])
		mx = sum([pow(v, 2) for v in self._d1.values()]) 
		my = sum([pow(v, 2) for v in self._d2.values()])

		return float(xy) / (mx + my - xy)

if __name__ == "__main__":
	#maybe need a test driver here
	prefs = {
		"fengbo" : { "1" : 3, "2" : 4 , "3" : 0, "4":3, "5":3},
		"fengbo2" : { "1" : 2, "2" : 3 , "3" : 2},
		"dafa" : {"1" : 2, "2" : 4, "3" : 4, "4":3, "5":0},
		"w" : {"1" : 0, "2" : 4, "3" : 0, "4": 2, "5":4}
	}
	"""
	print "euc: fengbo-dafa:", EucDistance(prefs, "fengbo", "dafa").similarity()
	print "euc: fengbo-w:", EucDistance(prefs, "fengbo", "w").similarity()
	print 
	"""

	print "pearson: fengbo-dafa:", Pearson(prefs, "fengbo", "dafa").similarity()
	print "pearson: fengbo-w:", Pearson(prefs, "fengbo", "w").similarity()
	print 

	print "pearson2: fengbo-dafa:", Pearson2(prefs, "fengbo", "dafa").similarity()
	print "pearson2: fengbo-w:", Pearson2(prefs, "fengbo", "w").similarity()
	print 

	print "cosine: fengbo-dafa:", Cosine(prefs, "fengbo", "dafa").similarity()
	print "cosine: fengbo-w:", Cosine(prefs, "fengbo", "w").similarity()
	print 

	"""
	print "tanimoto: fengbo-dafa:", Tanimoto(prefs, "fengbo", "dafa").similarity()
	print "tanimoto: fengbo-w:", Tanimoto(prefs, "fengbo", "w").similarity()
	"""
